﻿#include <iostream>
#include <fstream>
#include "json/json.h"
#include <algorithm>
#include <map>
#include <iomanip>
#include <cstdlib>
#include "Graph.h"
#include <string>
#include <sstream>
#include <vector>
#include <cstdio>
#include <queue>
#include <float.h>
#include "gp.hpp"
#include <assert.h>
#include <filesystem>
#include <random>
#include <numeric>
#include <ctime>

#include "sesson2_2.hpp"
using std::sort;
using namespace std;

bool Visited[MaxVertexNum] = { false };

void InsertEdge(LGraph Graph, Edge E);
LGraph CreateGraph(Graph &graph)
{ /* 初始化一个有VertexNum个顶点但没有边的图 */
	
	LGraph _Graph;

	_Graph = (LGraph)malloc(sizeof(struct GNode)); /* 建立图 */
	_Graph->Nv = graph.sum;
	_Graph->Ne = graph.edge_max_num;
	//   /* 初始化邻接表头指针 */
	//   /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
	for (Vertex V = 0; V < _Graph->Nv; V++)
	{
		_Graph->G[V].FirstEdge = NULL;
	}

	return _Graph;
}

void InsertEdge(LGraph Graph, Edgem E)
{
	PtrToAdjVNode NewNode;

	/* 插入边 <V1, V2> */
	/* 为V2建立新的邻接点 */
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V2;
	NewNode->Weight = E->Weight;
	/* 将V2插入V1的表头 */
	NewNode->Next = Graph->G[E->V1].FirstEdge;
	Graph->G[E->V1].FirstEdge = NewNode;

	/* 若是无向图，还要插入边 <V2, V1> */
	/* 为V1建立新的邻接点 */
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode->AdjV = E->V1;
	NewNode->Weight = E->Weight;
	/* 将V1插入V2的表头 */
	NewNode->Next = Graph->G[E->V2].FirstEdge;
	Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildGraph(LGraph &_Graph,Graph &graph)
{

	Edgem E;
	Vertex V;


	ReadJsonFromFile_edge("C:\\Users\\tang\\Desktop\\RHZT\\R1\\jsontest3\\map\\RoadLine.json", graph);
	//cout << graph.vnodes.size() << " edge  " << graph.node_index << endl;
	ReadJsonFromFile_point("C:\\Users\\tang\\Desktop\\RHZT\\R1\\jsontest3\\map\\RoadPoint.json", graph);

	_Graph = CreateGraph(graph);   /* 初始化有Nv个顶点但没有边的图 */
	_Graph->Ne = graph.edge_max_num; /* 读入边数 */
	if (_Graph->Ne != 0)
	{											 /* 如果有边 */
		E = (Edgem)malloc(sizeof(struct ENode)); /* 建立边结点 */
		/* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
		for (int i = 0; i < _Graph->Ne; i++)
		{
			//scanf_s("%d %d %d", &E->V1, &E->V2, &E->Weight);
			E->V1 = graph.edgemap1[i];
			E->V2 = graph.edgemap2[i];
	
			E->Weight = graph.weight[i];
			/* 注意：如果权重不是整型，Weight的读入格式要改 */
			InsertEdge(_Graph, E);
		}
	}

	/* 如果顶点有数据的话，读入数据 */
	//  for (V=0; V< _Graph->Nv; V++)
	//scanf_s(" %c", &(_Graph->G[V].Data));

	return _Graph;
}

void Visit(Vertex V)
{
	printf("%d ", V);
}

void InitVisited()
{
	for (int i = 0; i < MaxVertexNum; i++)
		Visited[i] = false;
}


/* Visited[]为全局变量，已经初始化为false */
void DFS(LGraph Graph, Vertex V, void (*Visit)(Vertex))
{ /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
	PtrToAdjVNode W;
	Visit(V);		   /* 访问第V个顶点 */
	Visited[V] = true; /* 标记V已访问 */
	for (W = Graph->G[V].FirstEdge; W; W = W->Next) /* 对V的每个邻接点W->AdjV */
		if (!Visited[W->AdjV])						/* 若W->AdjV未被访问 */
			DFS(Graph, W->AdjV, Visit);				/* 则递归访问之 */
}

//已用InitVisited();进行改进
Vertex listDFS(LGraph Graph, void (*Visit)(Vertex))
{
	Vertex i;
	for (i = 0; i < Graph->Nv; i++)
	{
		if (Visited[i] == false) //找出未被访问过的结点记录i值
			break;
	}
	if (i == Graph->Nv)
		return 0;
	DFS(Graph, i, Visit);
	printf("\n");
	return listDFS(Graph, Visit);
}
//图不连通时 列出各连通分量
void DFSListComponents(LGraph Graph, void (*Visit)(Vertex))
{
	for (Vertex i = 0; i < Graph->Nv; i++)
	{
		if (Visited[i] == false)
		{
			DFS(Graph, i, Visit);
			printf("\n");
		}
	}
}
int BFS(LGraph Graph, Vertex V, void (*Visit)(Vertex))
{
	queue<Vertex> Q;
	Vertex W;

	Visit(V);		   /* 访问第V个顶点 */
	Visited[V] = true; /* 标记V已访问 */
	Q.push(V);

	while (!Q.empty())
	{
		W = Q.front();
		Q.pop();
		for (PtrToAdjVNode tempV = Graph->G[W].FirstEdge; tempV; tempV = tempV->Next) /* 对W的每个邻接点tempV->AdjV */
			if (!Visited[tempV->AdjV])
			{
				Visited[tempV->AdjV] = true;
				Visit(tempV->AdjV);
				Q.push(tempV->AdjV);
			}
	}
	//已用 BFSListComponents进行改进
	//    printf("\n");
	//
	//    //遍历 Visited[]列出所有BFS的顶点 若只需一个顶点开始的BFS可忽略
	//    Vertex i;
	//    for(i = 0; i < Graph->Nv; i++) {
	//        if(Visited[i] == false)//找出未被访问过的结点记录i值
	//            break;
	//    }
	//    if(i == Graph->Nv)
	//        return 0;
	//    else
	//        return BFS(Graph,i,Visit);
	return 0;
}
//图不连通时 列出各连通分量
void BFSListComponents(LGraph Graph, void (*Visit)(Vertex))
{
	for (Vertex i = 0; i < Graph->Nv; i++)
	{
		if (Visited[i] == false)
		{
			BFS(Graph, i, Visit);
			printf("\n");
		}
	}
}
/* dist[]和path[]全部初始化为-1 */
void Unweighted(LGraph Graph, int dist[], int path[], Vertex S)
{
	queue<Vertex> Q;
	Vertex V;
	PtrToAdjVNode W;

	dist[S] = 0; /* 初始化源点 */
	Q.push(S);
	for (int i = 0; i < 16384; i++)
	{
		dist[i] = -1;
		path[i] = -1;
	}
	while (!Q.empty())
	{
		V = Q.front();
		Q.pop();
		for (W = Graph->G[V].FirstEdge; W; W = W->Next) /* 对V的每个邻接点W->AdjV */
		{
			if (dist[W->AdjV] == -1)
			{								 /* 若W->AdjV未被访问过 */
				dist[W->AdjV] = dist[V] + 1; /* W->AdjV到S的距离更新 */
				path[W->AdjV] = V;			 /* 将V记录在S到W->AdjV的路径上 */
				Q.push(W->AdjV);
			}
			// printf("%d,%d\n", W->AdjV, V);
		}
		//printf("%d,%d **********\n",0, 0);

	} /* while结束*/
}
#define INF 1e10 //权值上限
#define maxn 16384
int parent[maxn];	//每个顶点的父亲节点，可以用于还原最短路径树
bool visited[maxn]; //用于判断顶点是否已经在最短路径树中，或者说是否已找到最短路径
struct _node		//顶点节点，保存id和到源顶点的估算距离，优先队列需要的类型
{
	int id; //源顶点id和估算距离
	WeightType w;
	friend bool operator<(_node a, _node b) //因要实现最小堆，按升序排列，因而需要重载运算符，重定义优先级，以小为先
	{
		return a.w > b.w;
	}
};
_node d[maxn];			 //源点到每个顶点估算距离，最后结果为源点到所有顶点的最短路。
priority_queue<_node> q; //优先队列stl实现

bool Dijkstra(LGraph Graph, int s, int ed,vector<int> *vpaths,double *cost,_Path *pth) //Dijkstra算法，传入源顶点
{
	InitVisited();
	for (int i = 0; i < maxn; i++) //初始化
	{
		d[i].id = i;
		d[i].w = INF;		//估算距离置INF
		parent[i] = -1;		//每个顶点都无父亲节点
		visited[i] = false; //都未找到最短路
							//
	}

	d[s].w = 0;	  //源点到源点最短路权值为0
	q.push(d[s]); //压入队列中
	vector<int> sinpath;
	while (!q.empty()) //算法的核心，队列空说明完成了操作
	{
		_node cd = q.top(); //取最小估算距离顶点
		q.pop();
		int u = cd.id;
		if (visited[u]) //注意这一句的深意，避免很多不必要的操作
			continue;
		visited[u] = true;
		PtrToAdjVNode p = (Graph->G[u].FirstEdge); //松弛操作

		while (p != NULL) //找所有与他相邻的顶点，进行松弛操作，更新估算距离，压入队列。
		{
			int v = p->AdjV;
			if (!visited[v])// && d[v].w > d[u].w + p->Weight) //打开注释，为最短路径
			{
				d[v].w = d[u].w + p->Weight;
				parent[v] = u;//当前节点为u
				q.push(d[v]);
				//printf("%d,%d,%d\n", d[v].w,v,u);
			}
			p = p->Next;
		}
	}

	if (d[ed].w != INF)
	{
		vpaths->push_back(ed);
		for (int i = ed; i != s;)
		{
			int f = parent[i];
			vpaths->push_back(f);
			i = f;
		}
	

		*cost = d[ed].w;
		//printf("最短路径权值为：%f\n", d[ed].w);
		return true;
	}

	else
	{
		//printf("不存在从顶点%d到顶点%d的最短路径。\n", s, ed);
		return false;
	}
}

bool DijkstraMin(LGraph Graph, int s, int ed, vector<int>* vpaths, double* cost, _Path* pth) //Dijkstra算法，传入源顶点
{
	InitVisited();
	for (int i = 0; i < maxn; i++) //初始化
	{
		d[i].id = i;
		d[i].w = INF;		//估算距离置INF
		parent[i] = -1;		//每个顶点都无父亲节点
		visited[i] = false; //都未找到最短路
							//
	}

	d[s].w = 0;	  //源点到源点最短路权值为0
	q.push(d[s]); //压入队列中
	vector<int> sinpath;
	while (!q.empty()) //算法的核心，队列空说明完成了操作
	{
		_node cd = q.top(); //取最小估算距离顶点
		q.pop();
		int u = cd.id;
		if (visited[u]) //注意这一句的深意，避免很多不必要的操作
			continue;
		visited[u] = true;
		PtrToAdjVNode p = (Graph->G[u].FirstEdge); //松弛操作

		while (p != NULL) //找所有与他相邻的顶点，进行松弛操作，更新估算距离，压入队列。
		{
			int v = p->AdjV;
			if (!visited[v])// && d[v].w > d[u].w + p->Weight) //打开注释，为最短路径
			{
				d[v].w = d[u].w + p->Weight;
				parent[v] = u;//当前节点为u
				q.push(d[v]);
				//printf("%d,%d,%d\n", d[v].w,v,u);
			}
			p = p->Next;
		}
	}

	if (d[ed].w != INF)
	{
		vpaths->push_back(ed);
		for (int i = ed; i != s;)
		{
			int f = parent[i];
			vpaths->push_back(f);
			i = f;
		}


		*cost = d[ed].w;
		//printf("最短路径权值为：%f\n", d[ed].w);
		return true;
	}

	else
	{
		//printf("不存在从顶点%d到顶点%d的最短路径。\n", s, ed);
		return false;
	}
}
void finexy(LGraph &lgraph,Graph &graph,int id,double MAXVAL)
{
	int repr[2];
	for (int j = 0; j < graph.paths[id].vpaths[0].size() - 1; j++)
	{
		int ret0 = 0;
		int parent = graph.paths[id].vpaths[0][j];
		int sun = graph.paths[id].vpaths[0][j + 1];

		PtrToAdjVNode p = (lgraph->G[parent].FirstEdge); //松弛操作
		//cout << "parent:" << parent << " sun:" << sun;

		auto ret1 = std::find(graph.repect_point.begin(), graph.repect_point.end(), parent);
		if (ret1 == graph.repect_point.end())
		{
			//cout << parent << " not found" << endl;
		}
		else
		{
		//	cout << parent << " found it" << endl;
			repr[0] = parent;
			break;
		}

		while (p != NULL) //找所有与他相邻的顶点，进行松弛操作，更新估算距离，压入队列。
		{
			int v = p->AdjV;
		//	printf(" %d,%f ", v, p->Weight);

			auto ret = std::find(graph.repect_point.begin(), graph.repect_point.end(), v);
			if (ret == graph.repect_point.end())
			{
				//cout << v << " not found" << endl;
			}
			else
			{
			//	cout << v << " found it" << endl;
				if (v == sun)
				{
					ret0 = 1;
					repr[0] = v;

					break;
				}
			}
			p = p->Next;
		}
		if (ret0 == 1)
		{
			break;
		}
	}
	for (int j = graph.paths[id].vpaths[0].size() - 1; j > 0; j--)
	{
		int ret0 = 0;
		int parent = graph.paths[id].vpaths[0][j];
		int sun = graph.paths[id].vpaths[0][j + 1];

		PtrToAdjVNode p = (lgraph->G[parent].FirstEdge); //松弛操作
		auto ret1 = std::find(graph.repect_point.begin(), graph.repect_point.end(), parent);
		if (ret1 != graph.repect_point.end())
		{
			repr[1] = parent;
			break;
		}

		while (p != NULL) //找所有与他相邻的顶点，进行松弛操作，更新估算距离，压入队列。
		{
			int v = p->AdjV;
			auto ret = std::find(graph.repect_point.begin(), graph.repect_point.end(), v);
			if (ret != graph.repect_point.end())
			{
				if (v == sun)
				{
					ret0 = 1;
					repr[1] = v;
					break;
				}
			}
			p = p->Next;
		}
		if (ret0 == 1)
		{
			break;
		}
	}
	for (int j = graph.paths[id].vpaths[0].size() - 1; j > 0; j--)
	{
		int ret0 = 0;
		int parent = graph.paths[id].vpaths[0][j];
		int sun = graph.paths[id].vpaths[0][j + 1];
		if (parent == repr[1])
			continue;
		PtrToAdjVNode p = (lgraph->G[parent].FirstEdge); //松弛操作
	//	cout << "parent:" << parent << " sun:" << sun;


		while (p != NULL) //找所有与他相邻的顶点，进行松弛操作，更新估算距离，压入队列。
		{
			int v = p->AdjV;
			//printf(" %d,%f %f", v, p->Weight,1e8);
			p->Weight = MAXVAL ;
			if (repr[0] == sun)
			{
				ret0 = 1;
				break;
			}

			p = p->Next;
		}
		if (ret0 == 1)
		{
			break;
		}
	}
}
void paths2csv(vector<_Path> &paths,string save_path)
{
	ofstream file(save_path);

	//_Path& pth = paths[maxid];
	//int nums = 0;

	//for (int i = pth.vpaths[0].size() - 1; i >= 0; i--)
	//{
	//	if (i == pth.vpaths[0].size() - 1)
	//	{
	//		file << pth.vpaths[0][i];
	//	}
	//	else
	//	{
	//		file << "," << pth.vpaths[0][i];
	//	}
	//}
	//file << endl;


	for (int j = 0; j < 3; j++)//paths.size()
	{
		_Path& pth = paths[j];
		int nums = 0;
		cout << paths[j].weight << endl;
		for (int i = pth.vpaths[0].size() - 1; i >= 0; i--)
		{
			if (i == pth.vpaths[0].size() - 1)
			{
				file << pth.vpaths[0][i];
			}
			else
			{
				file << "," << pth.vpaths[0][i];
			}
		}
		file << endl;
	}
	file.close();
}
void check_pople(vector<_Path>& paths, Gen_Path &gp)
{
	for (int j = 0; j < paths.size(); j++)
	{
		_Path& pth = paths[j];
		int nums = 0;
		pth.weight = 0;
		for (int i = pth.vpaths[0].size() - 1; i >= 0; i--)
		{

				int val = gp.is_in_nodes(pth.vpaths[0][i]);
				if (val != -1)
				{

					if (nums >= 25)
						break;
					pth.weight += gp.ALL_peoples_points[val].people_type_weight;
					//printf("%d ", val);
					//printf("%d:%d ,%d  ",val, gp.ALL_peoples_points[val].people_type_weight, nums);
					nums++;
				}
		
		}
		//printf("%d w:%d ,%d  ", 0, pth.weight, nums);
		//cout << endl;

	}


}
vector<_Path> check_pople2(vector<_Path>& paths, Gen_Path& gp)
{
	vector<_Path> retpaths;
	for (int j = 0; j < 3; j++)
	{
		_Path& pth = paths[j];
		_Path retPth;
		int nums = 0;
		pth.weight = 0;
		for (int i = pth.vpaths[0].size() - 1; i >= 0; i--)
		{

			int val = gp.is_in_nodes(pth.vpaths[0][i]);
			if (val != -1)
			{

				if (nums >= 25)
					break;
				pth.weight += gp.ALL_peoples_points[val].people_type_weight;
				printf("%d ", val);
				retPth.vpaths[0].push_back(val);
				//printf("%d:%d ,%d  ",val, gp.ALL_peoples_points[val].people_type_weight, nums);
				nums++;
			}

		}
		retpaths.push_back(retPth);
		//printf("%d w:%d ,%d  ", 0, pth.weight, nums);
		cout << endl;

	}
	return retpaths;
}
extern "C" _declspec(dllexport)int  gen_people_25(int PATH_NUM = 1000)
{
	clock_t startTime, endTime;
	startTime = clock(); //计时开始
	Graph graph;
	string save_path = "C:\\Users\\tang\\Desktop\\cmd\\cpp_app\\data\\gen_people_25.csv";
	static LGraph  lgraph = BuildGraph(lgraph,graph);
	Gen_Path gp;
	uniform_int_distribution<int> distribution(0, gp.ALL_peoples_points.size() - 1);
	default_random_engine dre(static_cast<unsigned int>(startTime));//随机数引擎
	gp.gen_point_id(graph, gp.ALL_peoples_points);
	int start_end[3] = { 190, 10 };
	for (int i = 0; i < PATH_NUM; i++)
	{
		_Path* pth = new _Path;
		graph.paths.push_back(*pth);
		start_end[0] =gp.ALL_peoples_points[ distribution(dre)].node_id;
		start_end[1] = gp.ALL_peoples_points[distribution(dre)].node_id;
		bool ret = Dijkstra(lgraph,start_end[0], start_end[1], &graph.paths[i].vpaths[0], &graph.paths[i].cost[0], &graph.paths[i]);
		if (ret == false)
			continue;
		graph.paths[i].calEdge(graph.allEdgeswight);
		//graph.paths[i].print();

		//for (int j = 0; j < graph.paths[i].edges.size(); j++)
		//{
		//	graph.paths[i].distance += graph.allEdgeswight[graph.paths[i].edges[j]];
		//}
		//cout << graph.paths[i].distance << endl;
		finexy(lgraph, graph, i, DBL_MAX);
	}
	check_pople(graph.paths, gp);
	graph.minTimeSort();
	//vector<_Path> retpaths=check_pople2(graph.paths, gp);
	paths2csv(graph.paths,save_path);
	endTime = clock(); //计时结束
	cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s  " << endl;
	cout << "save_path:" << std::filesystem::current_path() << " " << save_path << endl;
	return 0;
}
extern "C" _declspec(dllexport)int  gen_differnent_paths(int _start=0,int _end=15000, int PATH_NUM = 10)
{
	clock_t startTime, endTime;
	startTime = clock(); //计时开始
	LGraph lgraph;
	Graph graph;
	string save_path = "./data/gen_10_paths.csv";

	lgraph = BuildGraph(lgraph, graph);
	for (int i = 0; i < PATH_NUM; i++)
	{
		_Path* pth = new _Path;
		graph.paths.push_back(*pth);
		bool ret = DijkstraMin(lgraph, _start, _end, &graph.paths[i].vpaths[0], &graph.paths[i].cost[0], &graph.paths[i]);
		graph.paths[i].calEdge(graph.allEdgeswight);
		graph.paths[i].print();

		for (int j = 0; j < graph.paths[i].edges.size(); j++)
		{
			graph.paths[i].distance += graph.allEdgeswight[graph.paths[i].edges[j]];
		}
		cout << graph.paths[i].distance << endl;

		finexy(lgraph, graph, i,1E20);
	}



	ofstream file(save_path);
	if (file)
	{
		for (int i = 0; i < graph.paths.size(); i++)
		{
			//	copy(graph.paths[i].vpaths[0].begin(), graph.paths[i].vpaths[0].end(), ostream_iterator<int>(cout, " ")); cout << "vpaths[0]" << endl;
			if (graph.paths[i].vpaths[0].size() < 1)
			{
				continue;
			}
			copy(graph.paths[i].vpaths[0].begin(), graph.paths[i].vpaths[0].end(), ostream_iterator<int>(file, ","));
			if (i <= graph.paths.size() - 1)
				file << i << endl;
			cout << "cost " << graph.paths[i].cost[0] + graph.paths[i].cost[1] << endl;
		}

	}
	file.close();
	cout << "size:" << graph.paths .size()<< endl; //输出vector中的内容

	endTime = clock(); //计时结束
	cout << "save_path:" << std::filesystem::current_path() << " " << save_path << endl;
	cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s  " << endl;
	//free(graph.pnodes);
	return 0;
}
extern "C" _declspec(dllexport)int  cpp_sum(int a,int b)
{
	return a + b;
}


extern "C" _declspec(dllexport)int  gen_randm_path(int num)
{
	clock_t startTime = clock(); //计时开始
	

	static Graph graph;
	static LGraph lgraph;
	BuildGraph(lgraph, graph);

	Gen_Path gp;
	gp.gen_point_id(graph);
	srand((unsigned)time(0));

	uniform_int_distribution<int> distribution(0, 15686);
	default_random_engine dre(static_cast<unsigned int>(time(nullptr)));//随机数引擎
	//for (int i = 0; i < 5; i++) {
	//	cout << distribution(dre) << endl;//生成随机数
	//}
	//cout << "" << endl;
	//dre.seed(100);
	//for (int i = 0; i < 5; i++) {
	//	cout << distribution(dre) << endl;//生成随机数
	//}


	int start_end[2] = {0, 10  };
	vector<_Path> paths;
	for (int j = 0; j < num; j++)
	{
			_Path *pth=new _Path;
			start_end[0] = distribution(dre) ;
			start_end[1] = distribution(dre) ;
			cout << start_end[0]<<"  "<< start_end[1] << endl;//生成随机数
			bool ret = Dijkstra(lgraph, start_end[0], start_end[1], &pth->vpaths[0], &pth->cost[0], pth);
			if (ret == true)
			{
				paths.push_back(*pth);
			}
			delete pth;
	}
	string save_path = "./gen_randm_path.csv";
	ofstream file(save_path);

	for (int j = 0; j < paths.size(); j++)
	{

		_Path& pth = paths[j];

			for (int i = pth.vpaths[0].size() - 1; i >= 0; i--)
			{
				//cout << pth.vpaths[0][i] << ",";
				if (i == pth.vpaths[0].size() - 1)
				{
					file << pth.vpaths[0][i];
				}
				else
				{
					file << "," << pth.vpaths[0][i];

				}
			}
			
			file << endl;
			cout << "j="<<j<<" "<< pth.vpaths[0].size() << endl;

		
	}
	file.close();
	cout << "save_path:" << std::filesystem::current_path() << " " << save_path << endl;
	double endTime = clock(); cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s  " << endl;
	return 0;
}
extern "C" _declspec(dllexport)int  gen_people_path(void)
{
	clock_t startTime = clock(); //计时开始
	static Graph graph;
	static LGraph lgraph;
	BuildGraph(lgraph,graph);

	Gen_Path gp;
	gp.gen_point_id(graph);

	
	int start_end[2] = {0, 10 };
	vector<_Path> paths[3];
	for (int j = 0; j < 3; j++)
	{
		for (int i = 0; i < 24; i++)
		{
			_Path pth ;
			
			Point ps = gp.peoples_point[j][i];
			Point pe = gp.peoples_point[j][i+1];
			start_end[0] = ps.node_id;
			start_end[1] = pe.node_id;
			printf("******* %d,%d\n", ps.node_id, pe.node_id);
			bool ret = Dijkstra(lgraph, start_end[0], start_end[1], &pth.vpaths[0], &pth.cost[0], &pth);
			if (ret == false)
			{
				cout << "NO PATH" << endl;
				pth.vpaths[0].push_back(pe.node_id);
				pth.vpaths[0].push_back(ps.node_id);
			}
			else
			{
				pth.vpaths[0].erase(pth.vpaths[0].begin());

			}
	
			pth.vpaths[0].erase(pth.vpaths[0].end()-1);
			
			
			paths[j].push_back(pth);
			
			graph.paths[i].calEdge(graph.allEdgeswight);
			graph.paths[i].print();
			finexy(lgraph, graph, i, DBL_MAX);
		}
	}

	ofstream file("./outpath.csv");
	
	for (int j=0;j<3;j++)
	{
		file << j;
		cout << paths[j].size() << endl;

			for (auto& pth : paths[j])
			{
				for (int i = pth.vpaths[0].size() - 1; i >= 0; i--)
				{
					cout << pth.vpaths[0][i] << ",";
					file << "," << pth.vpaths[0][i];
				}
			}
		file << endl;
	}
	file.close();
	double endTime = clock(); cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s  " << endl;

//
//	int mdm[2][3] = { {190, 10, 15550}, {110, 10000, 15000} };
//	int PATH_NUM = 10;

	//for (int i = 0; i < PATH_NUM; i++)
	//{
	//	_Path* pth = new _Path;
	//	graph.paths.push_back(*pth);
	//	bool ret = Dijkstra(lgraph, mdm[0][0], mdm[0][2], &graph.paths[i].vpaths[0], &graph.paths[i].cost[0], &graph.paths[i]);
	//	graph.paths[i].calEdge(graph.allEdgeswight);
	//	graph.paths[i].print();

	//	for (int j = 0; j < graph.paths[i].edges.size(); j++)
	//	{
	//		graph.paths[i].distance += graph.allEdgeswight[graph.paths[i].edges[j]];
	//	}
	//	cout << graph.paths[i].distance << endl;

	//	finexy(lgraph, graph, i);
	//}
	//ofstream file("./out.csv");
	//if (file)
	//{
	//	for (int i = 0; i < graph.paths.size(); i++)
	//	{
	//		//	copy(graph.paths[i].vpaths[0].begin(), graph.paths[i].vpaths[0].end(), ostream_iterator<int>(cout, " ")); cout << "vpaths[0]" << endl;
	//		if (graph.paths[i].vpaths[0].size() < 1)
	//		{
	//			continue;
	//		}
	//		copy(graph.paths[i].vpaths[0].begin(), graph.paths[i].vpaths[0].end(), ostream_iterator<int>(file, ","));
	//		if (i <= graph.paths.size() - 1)
	//			file << i << endl;
	//		cout << "cost " << graph.paths[i].cost[0] + graph.paths[i].cost[1] << endl;
	//	}

	//}
	//file.close();

	//endTime = clock(); //计时结束
	//cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s  " << endl;
	return 0;
}
extern "C" _declspec(dllexport)int  gen_all_path(int num)
{
	clock_t startTime = clock(); //计时开始
	static Graph graph;
	static LGraph lgraph;
	BuildGraph(lgraph, graph);

	Gen_Path gp;
	gp.gen_point_id(graph,gp.ALL_peoples_points);
	

	srand((unsigned)time(0));

	uniform_int_distribution<int> distribution(0, gp.ALL_peoples_points.size() - 1);
	default_random_engine dre(static_cast<unsigned int>(time(nullptr)));//随机数引擎


	int start_end[2] = { 0, 10 };
	vector<_Path> paths;
	for (int j = 0; j < num; j++)
	{
		
		_Path* pth = new _Path;
		start_end[0] = distribution(dre);
		start_end[1] = distribution(dre);
		Point &p1=gp.ALL_peoples_points[start_end[0]];
		Point& p2 = gp.ALL_peoples_points[start_end[1]];

		//cout << start_end[0] << "  " << start_end[1] << endl;//生成随机数
		bool ret = Dijkstra(lgraph, p1.node_id, p2.node_id, &pth->vpaths[0], &pth->cost[0], pth);
		if (ret == true)
		{
			paths.push_back(*pth);
		}
		delete pth;
	}

	string save_path = "./outrandmpath.csv";
	ofstream file(save_path);
	
	//cout<<" log "<<graph.is_in_nodes(3) << " log " << graph.is_in_nodes(47) <<endl;
	for (int j = 0; j < paths.size(); j++)
	{
		_Path& pth = paths[j];
		int mxn = 0;
		for (int i = pth.vpaths[0].size() - 1; i >= 0; i--)
		{
			if (i == pth.vpaths[0].size() - 1)
			{
				file << pth.vpaths[0][i];
			}
			else
			{
				file << "," << pth.vpaths[0][i];
				if (gp.is_in_nodes(pth.vpaths[0][i]) != -1)
					mxn++;
				
			}
		}
		cout <<mxn<< endl;
		file << endl;
	}
	file.close();
	cout << "save_path:" << std::filesystem::current_path() << " " << save_path << endl;
	double endTime = clock(); cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s  " << endl;
	return 0;
}
int main()
{
	//gen_all_path(1000);
	gen_differnent_paths(10,15000,10);
	//gen_people_25();


	return 0;
}
